import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=187 lang=java
 *
 * [187] 重复的DNA序列
 *
 * https://leetcode-cn.com/problems/repeated-dna-sequences/description/
 *
 * algorithms
 * Medium (42.88%)
 * Likes:    59
 * Dislikes: 0
 * Total Accepted:    9.8K
 * Total Submissions: 22.7K
 * Testcase Example:  '"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"'
 *
 * 所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA
 * 中的重复序列有时会对研究非常有帮助。
 *
 * 编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。
 *
 *
 *
 * 示例：
 *
 * 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 * 输出：["AAAAACCCCC", "CCCCCAAAAA"]
 *
 */

// @lc code=start
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> list = new HashSet<>();
        Set<String> set = new HashSet<>();
        for(int i=0; i <= s.length() - 10; i++) {
            if(set.contains(s.substring(i, i+10))) {
                list.add(s.substring(i, i+10));
            }
            set.add(s.substring(i, i+10));
        }
        List<String> res = new ArrayList<>();
        for(String ss : list)
            res.add(ss);
        return res;
    }
}
// @lc code=end

